The present invention relates to a method and apparatus for implementing electronic cash through utilization of an electrical communication system.
Electronic cash will probably come into wide use with a smart card as an electronic wallet. It is desirable, in such an instance, that electronic cash be stored as information in the electronic wallet without depending on any physical medium.
One possible approach to realizing electronic cash is to provide system security by physical means. The security protection of prepaid cards such as telephone cards is guaranteed mainly by difficulty in physically copying their magnetic records to other cards. However, recent scientific and technological advances have come to diminish or endanger the card security based on such a premise. Another disadvantage with this system is that electronic cash cannot be transferred as information over a communication line because it is always offered as a physical medium (magnetic card or the like).
Another approach is a scheme wherein customers use electronic ID cards such as credit cards (electronic credit cards or electronic checks) and settle accounts later on. With the electronic credit cards, the introduction of a digital signature as a substitute for a handwritten one enables their processing to be entirely electronized (computerized), permitting the transfer of settlement information over a communication line. With this system, however, it is impossible to ensure user privacy; the same goes for current credit cards and checks. That is to say, financial institutions that issue credit cards and settle accounts can freely get purchase histories of users and shops can also learn their credit card numbers and signatures.
The above-mentioned problems such as computerization of electronic cash, system security and user privacy could be solved by the combined use of a blind signature scheme (described in detail later) and an on-line check at the time of payment (a shop makes an on-line inquiry at the management center as to double/unauthorized spending of the electronic cash information presented by the user). This solution is, however, impractical taking into account that the access to the management center from the shop for each user's purchase involves such issues as the processing time (the user's waiting time), communication costs and on-line processing costs and data base maintenance and management costs at the management center. Hence, off-line processing is desirable for the processing at the time of cash payment.
There have been proposed electronic cash systems that permit off-line processing from the viewpoint of privacy protection, for example, in D. Chaum, A. Fiat and M. Naor, "Untraceable Electronic Cash," Advances in Cryptology-Crypt '88, Lecture Notes in Computer Science 403, pp. 319-327, Springer-Verlag, Berlin (1988), T. Okamoto et al, "Disposable Zero-Knowledge Authentications and Their Applications to Untraceable Electronic Cash," Advances in Cryptology-Crypt '89, Lecture Notes in Computer Science 435, pp.481-496, Springer-Verlag, Berlin (1989) and Japanese Pat. Appln. No. 88838/90 entitled "Method and Apparatus for Implementing Electronic Cash."
Now, a description will be given first of the blind signature scheme that is a basic technique for ensuring user privacy. The blind signature scheme has a signature attached by a signer to a document while keeping its contents secret. An RSA blind signature scheme is disclosed in U.S. Pat. No. 4,759,063 and D, Chaum, "Security without Identification: Transaction Systems to Make Big Brother Obsolete," Comm. Of the ACM, 28, 10, pp.1030-1044, and a blind signature scheme based on a zero knowledge interactive proof is described in T. Okamoto et al, "Divertible Zero-Knowledge Interactive Proofs and Commutative Random Self-Reducible," The Proc. Of Eurocrypt '89 (1989).
The blind signature demandant (user) creates a blind message x by randomizing the document m with a random number r through blind signature preprocessing. The signer calculates a provisional signature y corresponding to the blind message x through the use of a private key. At this time, the document m has been randomized by the blind message x, and hence is kept secret from the signer. The user excludes the influence of the random number r from the provisional signature y through blind signature postprocessing to obtain a true signature y' to the document m and sends a pair of document m and signature y' to a verifier, who uses a signer's public key to make a check to see if y' is the signature to the document m. The verifier cannot learn the correspondence between the provisional and true signatures y and y'.
Procedure for Blind Signature
Let A represent a signer, U a signature demandant and e.sub.A public information of the signer A. Let F represent a function indicating a blind signature preprocessing algorithm, D a function indicating a multiple blind signature algorithm and G a function indicating a blind signature postprocessing algorithm. The signer A uses the signature function D.sub.eA to generate a provisional signature .OMEGA.=De.sub.A (F.sub.eA (m.sub.1), . . . , F.sub.eA (m.sub.k)) from information created by the user US through the use of the preprocessing function functions F.sub.eA, then the user US performs blind signature postprocessing G.sub.eA on the provisional signature .OMEGA., thereby computing a true signature B=D.sub.eA (m.sub.1, . . . , m.sub.k) of the signer A for k messages m.sub.1, . . . , m.sub.k. This procedure is executed by the signer A and the user US to create the multiple blind signature as described below.
Step 1: The user US generates k blind messages x.sub.i ={F.sub.eA (m.sub.i).vertline.i=1,2, . . . ,k} from k messages {m.sub.i .vertline.i=1,2, . . . k} by the blind signature preprocessing F.sub.eA and sends the k blind messages to the signer A. In this instance, the respective blind messages x.sub.i =F.sub.eA (m.sub.i) are calculated independently and the function F.sub.eA uses a random number to keep m.sub.i secret.
Step 2: The signer A generates the provisional signature .OMEGA.=D.sub.eA (F.sub.eA (m.sub.1), . . . , F.sub.eA (m.sub.k)) from the k blind messages F.sub.eA (m.sub.1), . . . , F.sub.eA (m.sub.k) and sends it to the user US.
Step 3: The user US computes the true digital signature B=D.sub.eA (m.sub.1, . . . , m.sub.k) of the signer A corresponding to the messages m.sub.1, . . . , m.sub.k by blind signature postprocessing using the function G.sub.eA.
In the application of the RSA scheme to the blind signature, letting r.sub.i represent a random number and setting the blind message (blind signature preprocessing) x.sub.i, the provisional signature y and the blind signature postprocessing G.sub.eA as follows: EQU x.sub.i =F.sub.eA (m.sub.i)=r.sup.eA .times.m.sub.i mod n, EQU Y=.OMEGA.=D.sub.eA (x.sub.1, . . . , x.sub.k)=.pi..sub.1.ltoreq.i.ltoreq.k (xi).sup.dA mod n, EQU G.sub.eA (y)=.OMEGA./(r.sub.1 .times. . . . .times.r.sub.k)mod n,
the signature y becomes as follows: EQU Y=B=.pi..sub.1.ltoreq.I.ltoreq.k (m.sub.i).sup.dA mod n
In this case, the verification V.sub.eA (m.sub.1, . . . , m.sub.k, B) of the signature B for the messages m.sub.1, . . . , m.sub.k is conducted depending on whether it satisfies the following equation: EQU {.pi..sub.1.ltoreq.i.ltoreq.k (m.sub.i)}.sup.eA .tbd.B(modn)
If the equation is satisfied, then an output OK is provided. In the above, (e.sub.A,n) is a public key of the RSA scheme that the signer A uses, and letting P and Q represent large prime numbers, it satisfies the following equations: EQU n=P.times.Q EQU e.sub.A .times.d.sub.A .tbd.1(modL)
where: L=LCM{(P-1),(Q-1)} PA1 where (+) indicates an exclusive-OR. PA1 (1) a user sends a first institution public information N corresponding to his real name ID.sub.U and first secret information; PA1 (2) the first institution recognizes the user's identity, then generates a pseudonym I for the user and manages the correspondence between at least either one of the pseudonym I and the public information N and the real name ID.sub.U in secrecy; PA1 (3) the first institution attaches a signature to the public information N and the pseudonym I and sends the signature and the pseudonym I to the user; PA1 (4) the user obtain a license B from the signature sent from the first institution and stores it together with the pseudonym I; PA1 (5) the user uses the first secret information to calculate second secret information S corresponding to the pseudonym I and the public information N and holds the second secret information S; PA1 (6) the user sends information containing at least a random number and the license B and an amount of money A to a second institution to request it to issue electronic cash; PA1 (7) the second institution adds a signature to the received information containing the license B and sends it to the user as information containing electronic cash C; PA1 (8) the user checks the signed information from the second institution to see if the license B bears a signature for the public information N and the pseudonym I and if the electronic cash C is usable under the license B, thereafter making a payment to a third party through the use of the random number and the second secret information S; PA1 (9) the third party sends the second institution all information of communication with the user so as to seek a settlement concerning the electronic cash C; and PA1 (10) when there is a likelihood of an attack, the correspondence between at least either one of the pseudonym I and public information N and the real name ID.sub.U managed by the first institution is retrieved and the pseudonym I and the public information N are made public to preclude the possibility of the attack. PA1 (1) a user sends a first institution public information N corresponding to his real name ID.sub.U and secret information; PA1 (2) the first institution recognizes the user's identity, then generates a pseudonym I for the user and manages the correspondence between at least either one of the pseudonym I and the public information N and the real name ID.sub.U in secrecy; PA1 (3) the first institution attaches a signature to the public information N and the pseudonym I and sends the signature and the pseudonym I to the user; PA1 (4) the user obtains a license B from the signature sent from the first institution and stores it together with the pseudonym I; PA1 (5) the user sends information containing at least a random number b and the license B and an amount of money A to a second institution to request it to issue electronic cash; PA1 (6) the second institution adds a signature to the received information containing the license B and sends the user the signed information as information containing electronic cash C; PA1 (7) the user makes a check to see if the license B bears a signature for the public information N and the pseudonym I and if the electronic cash C is usable under the license B, thereafter making a payment to a third party through the use of the random number and the secret information S; PA1 (8) the third party sends the second institution all information of communication with the user so as to seek a settlement concerning the electronic cash C; and PA1 (9) when there is a likelihood of an attack, the correspondence between at least either one of the pseudonym I and public information N and the real name ID.sub.U managed by the first institution is retrieved and the pseudonym I and the public information N are made public to preclude the possibility of the attack. PA1 pseudonym generating means which receives from a user public information N and information containing the user's real name ID.sub.U and generates a pseudonym I corresponding to the real name ID.sub.U ; PA1 correspondence storage means which holds at least either one of the pseudonym I and the public information N and the real name ID.sub.U ; PA1 license signing means which uses a secret key for a license to sign, with a first signing function D.sub.eB, information containing the public information and the pseudonym I and sends the user the signed information as information containing a license B; and PA1 electronic cash signing means which signs, with a second signing function D.sub.eC, the information received from the user and containing the license B and sends the user the signed information as electronic cash information.
Where L=LCM{a,b} represents the least common multiple of a and b and a.tbd.b(mod n) indicates that (a-b) is a multiple of n. When P and Q are very large prime numbers, it is very difficult, in general, to obtain P and Q by factoring n. Accordingly, even if n is made public, P and Q can be kept secret. In the following description, d.sub.A will sometimes be expressed as 1/e.sub.A. The Chaum-Fiat-Naor scheme will be described below on the assumption that k&gt;1, and embodiments of the present invention will be described on the assumption that k=1.
An example of the configuration of the RSA cryptography is described in Rivest, R. L. Et al, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, Vol. 21, No. 2, pp.120-126(1978).
Methods for constructing the blind signature scheme are disclosed in, for example, Chaum, D., "Blind Signature systems," U.S. Pat. No. 4,759,063 and Ohta, K. Et al, "Authentication system and Apparatus Therefor," U.S. Pat. No. 4,969,189.
The user privacy can be guaranteed by the use of the blind signature solely on the user's own responsibility. That is, since the user adds and remove the random number r to and from the blind signature, no one can learn the correspondence between y=.OMEGA. and y'=B as long as the random number r is kept secret. However, it is pointed out in S. Von Solms and D. Naccache, "On Blind Signature and Perfect Crimes," Computers and Security, 11, pp.581-583 (1992) that there is a fear of the scheme being abused for perfect crimes of money laundering and kidnapping because the scheme can make the flow of money completely untraceable.
Next, a description will be given of electronic cash issue processing between a bank and a customer, payment with electronic cash by the customer at a shop and settlement processing between the shop and the bank in the Chaum.multidot.Fiat.multidot.Naor scheme that is a typical electronic cash scheme.
Processing for Issuing Electronic Cash
A procedure will be described which the user US follows to have a bank BK issue electronic cash C. Now, let ID represent identification information of the user US and eA a public key for a digital signature of the bank BK corresponding to the amount of money (ten thousand yen, for instance) of electronic cash specified that the user US specifies. The user US gets the bank BK to issue electronic cash as described below.
Step 1: The user US creates a predetermined random number a.sub.i (where i=1, . . . , K) and then calculates x.sub.i and y.sub.i using a one-way function g made public as follows: EQU x.sub.i =g(a.sub.i) EQU y.sub.i =g(a.sub.i (+)ID)
Step 2: The user US calculates W.sub.i using a one-way function f made public and a blind signature preprocessing function F.sub.eA and presents it to the bank BK. EQU W.sub.i =F.sub.eA (f(x.sub.i,Y.sub.i)
Step 3: The bank BK selects K/2 subsets H+={i.sub.j } (where j=1, . . . ,K/2 and 1.ltoreq.i.sub.j .ltoreq.K) randomly among 1 to K and sends them as a disclosure request to the user US. For the brevity of description, let it be assumed that H={K/2+1,K/2+2, . . . ,K} is designated as the disclosure request. A procedure for requesting the disclosure of K/2 subsets randomly selected from K subsets is called a cut-and-choose method.
Step 4: Upon receiving the disclosure request from the bank BK, the user US discloses to the bank BK the requested K/2 random numbers a.sub.i and the random number a.sub.i used in the function F.sub.eA to calculate W.sub.i.
Step 5: The bank BK verifies the validity of all of the disclosed K/2 groups and, if any one of the verifications fails, halts the subsequent processing. When all the verifications succeed, the bank BK performs the following procedure for i (where i=1,2, . . . K/2) which are not the object of disclosure.
Step 6: The bank BK calculates and sends .OMEGA. to the user US. EQU .OMEGA.=D.sub.eA (W.sub.1, . . . ,W.sub.K /2)
Step 7: The user US calculates the electronic cash C from the data .OMEGA. received from the bank BK as follows: EQU C=G.sub.eA (.OMEGA.)=D.sub.eA (f(x.sub.1,y.sub.1), . . . , f(x.sub.K/2,y.sub.K/2))
Payment with Electronic Cash
Next, a description will be given of how the user US makes a payment to a shop SH with the electronic cash C issued from the bank BK. The following processing is carried out for each i (where i=1,2, . . . ,K/2).
Step 1: The user sends the electronic cash C to the shop SH.
Step 2: The shop SH creates a random bit e.sub.i and sends it to the user US.
Step 3: The user supplies the shop SH with a.sub.i and y.sub.i when e.sub.i =1 and x.sub.i and a.sub.i (+)ID when e.sub.i =0.
Step 4: The shop SH uses the public key e.sub.A of the bank BK to check if the electronic cash C bears a correct signature for the messages f(x.sub.1,y.sub.1), . . . , f(x.sub.K/2,y.sub.K/2).
Settlement
Finally, a description will be given of the settlement of an account between the shop SH and the bank BK. The shop SH presents to the bank BK a history H of communications conducted with the user US when he used the electronic cash C. The bank BK verifies the validity of the communication history H and, if it passes the verification, stores the history H and pays the money into the shop's account. Alternatively, the bank BK pays the money by some other means. When finding an unauthorized use of electronic cash, the bank BK searches the stored communication history for the data ai and a.sub.i (+)ID corresponding to the electronic cash and decides the identification information ID of the malicious adversary.
According to the Chaum-Fiat-Naor scheme, the user US supplies the shop SH with the data ai or a.sub.i (+)ID depending on whether the random bit e.sub.i generated at the time of payment with the electronic cash is "1" or "0"; hence, when the user US uses the electronic cash C twice without proper authorization and i-th random bits e.sub.i sent to the shop SH first and second times differ, the data ai and a.sub.i (+)ID are passed to the bank BK, which can detect the user's identification information by calculating a.sub.i (+)(a.sub.i (+)ID)=ID from the data supplied thereto. Since the bank BK makes an inquiry about K/2 bits, the probability of failure in the detection of double spending of the cash C is 2.sup.-K/1. Usually, it is recommended that K=20 or so.
Since the electronic cash system employing the afore-mentioned blind signature scheme can make the flow of electronic cash untraceable unconditionally, the privacy of the electronic cash user is guaranteed solely on his own responsibility. That is, since the user himself adds to and removes from the blind signature the random number r for randomization, there is no possibility that anyone can learn the correspondence between the provisional and true signatures y and y' as long as the random number r is kept secret. As pointed out in the aforementioned literature by S. Von Solms and D. Naccahe, however, there is a fear that this scheme having such an unconditional anonymity feature could be abused for perfect crimes of money laundering and kidnapping because this system can make the flow of cash completely untraceable. The same goes for the electronic cash system described in Okta et al. U.S. Pat. No. 4,977,595.